﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class DCube
    {
        private int minValue = 8000000;
        public DCube()
        {
            int T = GetConsole.GetInt();
            while (T-- > 0)
            {
                minValue = 8000000;

                int[] size = new int[3];
                size[0] = GetConsole.GetInt();
                size[1] = GetConsole.GetInt();
                size[2] = GetConsole.GetInt();
                SortSize(size);
                if (size[0] == size[1] && size[1] == size[2])
                {
                    minValue = 0;
                    Console.WriteLine(minValue);
                    continue;
                }
                for (int i = size[0]/2; i >= 1; i--)
                {
                    List<int[]> sizeList = new List<int[]>();
                    sizeList.Add(size);
                    Cutting(size, 1, i, sizeList, new List<int[]>(), new List<int>());
                }
                Console.WriteLine(minValue);

            }
        }
        public void Cutting(int[] size, int count, int point, List<int[]> sizeList, List<int[]> answerList, List<int> countList)
        {
            count++;
            if (count > minValue)
            {
                return;
            }
            sizeList.RemoveAt(sizeList.Count - 1);
            int[] size1 = new int[3] { point, size[1], size[2] };
            if (size1[0] != size1[1] || size1[1] != size1[2])
            {
                SortSize(size1);
                sizeList.Add(size1);
            }
            else
            {
                answerList.Add(size1);
                countList.Add(count);
            }
            int[] size2 = new int[3] { size[0] - point, size[1], size[2] };
            if (size2[0] != size2[1] || size2[1] != size2[2])
            {
                SortSize(size2);
                sizeList.Add(size2);
            }
            else
            {
                answerList.Add(size2);
                countList.Add(count);
            }
            if (sizeList.Count == 0)
            {
                if (count < minValue)
                {
                    minValue = count;
                }
                return;
            }

            for (int i = sizeList[sizeList.Count-1][0] / 2; i >= 1; i--)
            {
                List<int[]> newSizeList = new List<int[]>(sizeList);
                List<int[]> newAnswerList = new List<int[]>(answerList);
                List<int> newCountList = new List<int>(countList);
                Cutting(sizeList[sizeList.Count-1], count, i, newSizeList, answerList, countList);
            }
        }

        public void SortSize(int[] size)
        {
            int buf = 0;
            if (size[0] < size[1])
            {
                buf = size[0];
                size[0] = size[1];
                size[1] = buf;
            }
            if (size[1] < size[2])
            {
                buf = size[1];
                size[1] = size[2];
                size[2] = buf;
            }
            if (size[0] < size[1])
            {
                buf = size[0];
                size[0] = size[1];
                size[1] = buf;
            }

        }
        public int GetMaxIndex(int[] size)
        {
            if (size[0] > size[1])
            {
                if (size[0] > size[2])
                { return 0; }
                else
                { return 2; }
            }
            else
            {
                if (size[1] > size[2])
                { return 1; }
                else
                { return 2; }
            }
        }
    }
}
